Paper 2023/1216

Unlocking the lookup singularity with Lasso

Srinath Setty, Microsoft Research
Justin Thaler, a16 crypto research and Georgetown University
Riad Wahby, Carnegie Mellon University
Abstract

This paper introduces Lasso, a new family of lookup arguments, which allow an untrusted prover to commit to a vector $a \in \mathbb{F}^m$ and prove that all entries of a reside in some predetermined table $t \in \mathbb{F}^n$. Lasso’s performance characteristics unlock the so-called "lookup singularity". Lasso works with any multilinear polynomial commitment scheme, and provides the following efficiency properties. For $m$ lookups into a table of size $n$, Lasso’s prover commits to just $m + n$ field elements. Moreover, the committed field elements are small, meaning that, no matter how big the field $\mathbb{F}$ is, they are all in the set $\{0, . . . , m\}$. When using a multiexponentiation-based commitment scheme, this results in the prover’s costs dominated by only $O(m + n)$ group operations (e.g., elliptic curve point additions), plus the cost to prove an evaluation of a multilinear polynomial whose evaluations over the Boolean hypercube are the table entries. This represents a significant improvement in prover costs over prior lookup arguments (e.g., plookup, Halo2’s lookups, lookup arguments based on logarithmic derivatives). Unlike all prior lookup arguments, if the table $t$ is structured (in a precise sense that we define), then no party needs to commit to $t$, enabling the use of much larger tables than prior works (e.g., of size $2^{128}$ or larger). Moreover, Lasso’s prover only "pays" in runtime for table entries that are accessed by the lookup operations. This applies to tables commonly used to implement range checks, bitwise operations, big-number arithmetic, and even transitions of a full-fledged CPU such as RISC-V. Specifically, for any integer parameter $c > 1$, Lasso’s prover’s dominant cost is committing to $3 \cdot c \cdot m + c \cdot n^{1/c}$ field elements. Furthermore, all these field elements are “small”, meaning they are in the set $\{0, . . . , \max{(m, n^{1/c}, q)} − 1\}$, where $q$ is the maximum value in $a$. Lasso’s starting point is Spark, a time-optimal polynomial commitment scheme for sparse polynomials in Spartan (CRYPTO 2020). We first provide a stronger security analysis for Spark. Spartan’s security analysis assumed that certain metadata associated with a sparse polynomial is committed by an honest party (this is acceptable for its purpose in Spartan, but not for Lasso). We prove that Spark remains secure even when that metadata is committed by a malicious party. This provides the first "standard" commitment scheme for sparse multilinear polynomials with optimal prover costs. We then generalize Spark to directly support a lookup argument for both structured and unstructured tables, with the efficiency characteristics noted above.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
lookup argumentssuccinct argumentssparse polynomial commitments
Contact author(s)
srinath @ microsoft com
History
2023-08-11: approved
2023-08-10: received
See all versions
Short URL
https://ia.cr/2023/1216
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1216,
      author = {Srinath Setty and Justin Thaler and Riad Wahby},
      title = {Unlocking the lookup singularity with Lasso},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1216},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1216}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.